package mianshi.leetcode.dp.medium;

/**
 * m*n的网格，从左上角到右下角有多少种方法(没有障碍物)
 */
public class MN表格左上右下走法有障碍物63 {
    public static void main(String[] args) {

    }
    //没有障碍物
    public static int test(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = 1;
                } else if (i == 0) {

                    dp[i][j] = dp[i][j - 1];
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                }

            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 有障碍物的时候
     * @param dpobstacleGrid
     * @return
     */
    public static int uniquePathsWithObstacles(int[][] dpobstacleGrid) {
        for (int i = 0; i < dpobstacleGrid.length; i++) {
            for (int j = 0; j < dpobstacleGrid[0].length; j++) {
                //有障碍物时，当前值设为0
                if (dpobstacleGrid[i][j] == 1) {
                    dpobstacleGrid[i][j] = 0;
                    continue;
                }
                if (i == 0 && j == 0) {
                    dpobstacleGrid[i][j] = 1;
                } else if (i == 0) {

                    dpobstacleGrid[i][j] = dpobstacleGrid[i][j - 1];
                } else if (j == 0) {
                    dpobstacleGrid[i][j] = dpobstacleGrid[i - 1][j];
                } else {
                    dpobstacleGrid[i][j] = dpobstacleGrid[i][j - 1] + dpobstacleGrid[i - 1][j];
                }

            }
        }
        return dpobstacleGrid[dpobstacleGrid.length - 1][dpobstacleGrid[0].length - 1];
    }

}
